package 数据结构设计高频题;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 最大频率栈
// 测试链接 : https://leetcode.cn/problems/maximum-frequency-stack/
public class Code06_MaximumFrequencyStack {

    class FreqStack {
        // 出现的最大次数
        private int topTimes;
        // 每一个数出现了几次
        private HashMap<Integer, Integer> valueTimes = new HashMap<>();
        // 每层节点
        private HashMap<Integer, ArrayList<Integer>> cntValues = new HashMap<>();

        public void push(int val) {
            // 如果频率表中已经有该元素，则更新，否则增加
            valueTimes.put(val, valueTimes.getOrDefault(val, 0) + 1);
            int curValTopTimes = valueTimes.get(val);
            if(!cntValues.containsKey(curValTopTimes)){
                cntValues.put(curValTopTimes, new ArrayList<>());
            }
            ArrayList<Integer> curTimeValues = cntValues.get(curValTopTimes);
            curTimeValues.add(val);
            topTimes = Math.max(topTimes, curValTopTimes);
        }

        public int pop() {
            ArrayList<Integer> topTimeValues = cntValues.get(topTimes);
            int ans = topTimeValues.remove(topTimeValues.size() - 1);
            if(topTimeValues.size() == 0){
                cntValues.remove(topTimes--);
            }
            int removeValTimes = valueTimes.get(ans);
            if(removeValTimes == 1){
                valueTimes.remove(ans);
            }else {
                valueTimes.put(ans, removeValTimes-1);
            }
            return ans;
        }
    }
}
